# @Time : 2020/9/8 15:15
# @Author : Fioman 
# @Phone : 13149920693

"""
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

 

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5
"""
from typing import List


class Solution(object):
    # 遍历数组1和数组2,都吃从小到大去遍历.记录下数组的最小值还有最大值.
    def find_media_sorted_arrays(self,nums1:List[int],nums2:List[int]) -> float:
        newArray = []
        m = len(nums1)
        n = len(nums2)
        length = m + n
        mid = length // 2
        i,j = 0,0
        while len(newArray) - 1 < mid:
            if i <m and j < n:
                if nums1[i] < nums2[j]:
                    newArray.append(nums1[i])
                    i += 1
                    continue

                if nums1[i] >= nums2[j]:
                    newArray.append(nums2[j])
                    j += 1
                    continue

            if i == m and j < n:
                while j < n and len(newArray) - 1 < mid:
                    newArray.append(nums2[j])
                    j += 1

            if i < m and j == n:
                while i < m and len(newArray) - 1 < mid:
                    newArray.append(nums1[i])
                    i += 1

            if length & 1:
                res = newArray[mid]
            else:
                res = (newArray[mid-1] + newArray[mid]) / 2
            return res





if __name__ == '__main__':
    nums1 = [1,2,3]
    nums2 = [4,5,6]
    s = Solution()
    media = s.find_media_sorted_arrays(nums1,nums2)
    print(media)

